//
// Created by dxyinme on 2021/10/2.
//

#pragma once

#include "v_list.h"
#include "v_util.h"
#include "thread_pool.h"
#include <future>
#include <vector>
#include <iostream>
#include <sstream>

namespace Vsort {
// ------------------------------------------declare

// return the ptr of the last of left part.
template <typename T>
VListNode<T>* GetMiddle(VListNode<T>* h);

template <typename T>
VListNode<T>* MergeVList(VListNode<T>* h1, VListNode<T>* h2);

template <typename T>
VListNode<T>* SortVList(VListNode<T>* h);

template<typename T>
VListNode<T>* SortVListExThread(
        VListNode<T>* h,
        std::size_t each_thread_sort_size,
        ThreadPool* thPool);

template <typename T>
void DeleteVList(VListNode<T>* h);

template<typename T>
void MergeVLists(std::vector<VListNode<T>*>& merge_lists, ThreadPool* thPool);

// ------------------------------------------define
template <typename T>
VListNode<T>* GetMiddle(VListNode<T>* h) {
  auto* o_1_step = h;
  auto* o_2_step = h;
  while (o_1_step != nullptr && o_2_step != nullptr) {
    o_2_step = o_2_step->nxt;
    if (o_2_step != nullptr) {
      o_2_step = o_2_step->nxt;
    }
    if (o_2_step == nullptr) {
      break ;
    }
    o_1_step = o_1_step->nxt;
  }
  return o_1_step;
}

template <typename T>
VListNode<T>* MergeVList(VListNode<T>* h1, VListNode<T>* h2) {
  if (h1 == nullptr) return h2;
  if (h2 == nullptr) return h1;
  auto* tmpNode = new VListNode<T>();
  auto* ansTmpNode = tmpNode;
  while (h1 != nullptr && h2 != nullptr) {
    if (h1->val < h2->val) {
      tmpNode->nxt = h1;
      tmpNode = tmpNode->nxt;
      h1 = h1->nxt;
    } else {
      tmpNode->nxt = h2;
      tmpNode = tmpNode->nxt;
      h2 = h2->nxt;
    }
  }
  if (h1 != nullptr) tmpNode->nxt = h1;
  if (h2 != nullptr) tmpNode->nxt = h2;
  auto* ans = ansTmpNode->nxt;
  delete ansTmpNode;
  return ans;
}

template <typename T>
VListNode<T>* SortVList(VListNode<T>* h) {
  if (h == nullptr || h->nxt == nullptr) {
    return h;
  }
  auto* lEnd = GetMiddle(h);
  auto* rBegin = lEnd->nxt;
  lEnd->nxt = nullptr;
  auto* lRes = SortVList(h);
  auto* rRes = SortVList(rBegin);
  return MergeVList(lRes, rRes);
}

template <typename T>
void DeleteVList(VListNode<T>* h) {
  if (h != nullptr) {
    DeleteVList(h->nxt);
    delete h;
  }
}

template<typename T>
VListNode<T>* SortVListExThread(VListNode<T>* h, std::size_t each_thread_sort_size, ThreadPool* thPool) {
  std::vector<std::future<VListNode<T>*>> result_each_thread;
  while (true) {
    size_t cnt = 1;
    auto* now_head = h;
    auto* tmp_head = h;
    bool break_flag = false;
    while (h->nxt != nullptr && cnt < each_thread_sort_size) {
      h = h->nxt;
      cnt++;
    }
    if (h->nxt == nullptr) {
      break_flag = true;
    }
    tmp_head = h->nxt;
    h->nxt = nullptr;
    result_each_thread.emplace_back(thPool->enqueue([now_head] {
        auto* res_sub_th = SortVList(now_head);
        return res_sub_th;
      }));
    if (break_flag) {
      break;
    }
    h = tmp_head;
  }

  std::vector<VListNode<T>*> results;
  for (auto&& item : result_each_thread) {
    results.emplace_back(item.get());
  }
  MergeVLists(results, thPool);
  return results.front();
}

template<typename T>
void MergeVLists(std::vector<VListNode<T>*>& merge_lists, ThreadPool* thPool) {
  while (merge_lists.size() > 1) {
    std::vector<VListNode<T>*> tmp;
    std::vector<std::future<void>> tasks;
    for (int i = 0; i < merge_lists.size(); i+=2) {
      if (i + 1 < merge_lists.size()) {
        tasks.emplace_back(thPool->enqueue([&tmp, &merge_lists] (int i) {
          tmp.emplace_back(MergeVList(merge_lists[i], merge_lists[i + 1]));
        }, i));
      } else {
        tmp.emplace_back(merge_lists[i]);
      }
    }
    for (auto&& item : tasks) item.get();
    merge_lists.assign(tmp.begin(), tmp.end());
  }
}

}

